Control methods are used by commercial database systems to provide for concurrent access to the database systems. It is common for many database users to seek concurrent access to an information retrieval system in order to read data from the database and write data to the database. Concurrency control methods are used to manage the users and the users' requests.
The main concurrency control methods employed by commercial database systems are locking techniques. The book by H. F. Korth and A. Silberschatz, entitled Database System Concepts, McGraw-Hill, 1991, which is incorporated herein by reference for its teaching on database systems, gives a detailed review of locking protocols. In such schemes, each data item has a number of locks associated with it. A transaction wishing to read that item must first acquire the corresponding read lock. Similarly, before an update, a write lock must be requested. A number of transactions may obtain concurrent read locks, but only if no other transaction is currently holding a write lock. Write locks can only be granted to one requester at a time. When the transaction has finished accessing the data item, it releases the locks which guard that item.
The most widely used locking protocol is two-phase locking as discussed in K. P Eswaran et al., "The Notions of Consistency and Predicate Locks in a Data Base System", Communications of the ACM, November 1976, which is incorporated herein by reference for its teachings on database systems. This method prohibits a transaction from requesting any new locks until that transaction has released any old locks.
Another class of widely-studied concurrency control methods involves timestamp protocols as discussed in D. Reed, "Implementing Atomic Actions on Decentralized Data", ACM Transactions on Computer Systems, February 1983, which is incorporated herein by reference for its teachings on database systems. This timestamp concurrency control method requires that a transaction acquire a unique timestamp before starting execution. Each data item has two values associated with it: (1) a write timestamp, which denotes the latest timestamp of any transaction that ever updated the item, and (2) a read timestamp, which consists of the latest timestamp of any transaction that ever read the associated data. The use of these timestamps guarantees that the transactions are executed in sequential order without read/write conflicts.
A typical timestamp-based scheme would work as follows. Suppose a transaction T tries to read an item which has an update timestamp that is more recent than T's timestamp. This means that T is trying to read data written by a transaction that started after T; i.e., the value that T should have read has already been overwritten by a subsequent transaction. Thus, transaction T must be aborted and restarted with a new timestamp.
There are a number of variations on the timestamp theme. A well-known technique is the wait-die protocol, discussed in D. J. Rosenkrantz et al., "System Level Concurrency Control for Distributed Database Systems", ACM Transactions on Database Systems, June 1978, which is incorporated herein by reference for its teachings on database systems. Under this scheme, if a transaction T1 needs to access an item, either for reading or writing, and the item is protected by locks that are already held by transaction T2, T1 is allowed to wait for the item only if its timestamp is smaller than that of T2, i.e., if T1 is older than T2. Otherwise, T1 is rolled back. A second variation is the wound-wait protocol, also discussed in Rosenkrantz, in which transactions are only allowed to wait for items held by older transactions, otherwise the transaction holding the item is rolled back and the item is released. Again, see the book by Korth and Silberschatz, entitled Database System Concepts, for a detailed review of timestamp protocols.
A third class of concurrency control methods has been developed for real time databases, R. Abbott and H. Garcia-Molina, "Scheduling Real-Time Transactions: A Performance Evaluation", Proceedings of the 14th International Conference on Very Large Databases, 1988, which is incorporated herein by reference for its teachings on database systems. Transactions in such database management systems must finish before their deadlines. Thus, concurrency control methods for such systems attempt to schedule transactions in such a way that all, or at least most, finish completely before their deadlines. A typical scheme consists of giving preference to high priority transactions. A higher priority transaction which needs to access data held by a lower priority transaction forces the lower priority transaction to abort, and a lower priority transaction waits for a higher priority transaction to release the data. The priorities considered are first-come-first-served, earliest deadline, and least slack. Slack is an estimate of how long the transaction can be delayed and its deadline still met. First-come-first-served and earliest deadline assign fixed priorities, while the priorities assigned under least slack are constantly increasing.